Ngay ở giai đoạn hình thành, trung đoàn Fedko (lúc đó là biệt đội Biển Đen số 1) đã thực hiện một cuộc đột kích qua Bắc Tavria và Nikolayevshchina và tham gia cuộc nổi dậy Nikolaev vào ngày 20-23 tháng 3 năm 1918. Sau thất bại của cuộc nổi dậy, trung đoàn của Fedko đã chiến đấu chống lại quân Đức ở Bắc Tavria và Crimea cho đến ngày 1 tháng 5.

Trong cuộc Nội chiến Nga, ông đã chiến đấu ở Bắc Caucasus. Từ tháng 5 đến tháng 10 năm 1918, ông chỉ huy các đội quan thứ ba và đầu tiên của quân Bắc Caucasus. Từ ngày 27 tháng 10 đến tháng 11 năm 1918, ông được bổ nhiệm làm quyền Tổng chỉ huy quân cách mạng Bắc Caucasus. Vào tháng 11 năm 1918 - tháng 2 năm 1919, ông làm là trợ lý tư lệnh quân đoàn 11. Năm 1919, Fedko trở thành thành viên của RVS Cộng hòa xã hội chủ nghĩa Xô viết Crimea và là phó chỉ huy quân đội Crimea thuộc Tập đoàn quân 14. Ông trải qua nhiều cương vị khác nhau và tham gia nhiều trận đánh. Nhờ tài năng và quân công, ông đã bốn lần được tặng Huân chương Cờ đỏ.

Từ tháng 5 năm 1937 đến tháng 1 năm 1938 - Chỉ huy trưởng Quân khu Kiev. Từ tháng 1 năm 1938 - Phó Chính ủy Quốc phòng thứ nhất của Liên Xô. Đồng thời, từ tháng 3 năm 1938, ông là Ủy viên Hội đồng Quân chính của Hồng quân.

Năm 1937, ông được bầu làm Phó Chủ tịch Xô viết Tối cao Liên Xô trong cuộc triệu tập đầu tiên, và tại phiên họp thứ nhất vào tháng 1 năm 1938 - là thành viên của Đoàn Chủ tịch Xô Viết Tối cao Liên Xô.